#include <iostream>
#include <unordered_set>
using namespace std;
// Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        unordered_set<ListNode *> u_set;
        while (headA || headB)
        {
            if (headA)
                if (!u_set.insert(headA).second)
                    return headA;
            if (headB)
                if (!u_set.insert(headB).second)
                    return headB;
            if (headA)
                headA = headA->next;
            if (headB)
                headB = headB->next;
        }
        return nullptr;
    }
};